package com.xsherl.leetcode.solution;

public class MultiplyStrings {

    public static final String ZERO = "0";

    /**
     * 新建一个int数组来存放结果每一位的值
     * 计算每一位的乘积，然后加上int数组中的值，在数组中存放个位，
     * 返回字符串不包含前缀0
     */
    public String multiply(String num1, String num2) {
        if (num1.equals(ZERO) || num2.equals(ZERO)){
            return ZERO;
        }
        int len1 = num1.length(), len2 = num2.length();
        int[] res = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; --i){
            int a = num1.charAt(i) - '0';
            int carry = 0;
            int j = len2 - 1;
            while (carry > 0 || j >= 0){
                int b = j >= 0 ? num2.charAt(j) - '0' : 0;
                int bitIndex = i + j + 1;
                int n = a * b + carry + res[bitIndex];
                carry = n / 10;
                res[bitIndex] = n % 10;
                j--;
            }
        }
        StringBuilder sb = new StringBuilder(res.length);
        int i = 0;
        while (res[i] == 0){
            i++;
        }
        while (i < res.length) {
            sb.append(res[i++]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String num1 = "1230";
        String num2 = "4561";
        String multiply = new MultiplyStrings().multiply(num1, num2);
        System.out.println(multiply);
    }
}
